A polynomial is a mathematical function involving the sum of powers of a function variable, x, multiplied by coefficients a0, a1, a2, . . . , an. A polynomial has the general analytic formf(x)=anxn+ . . . +a2x2+a1x+a0.The degree of a polynomial is the number n characterizing the largest power of the polynomial.
The ratio of two polynomial functions is called a rational function. If f(x) and g(x) are two polynomial functions, then
      h    ⁡          (      x      )        =            f      ⁡              (        x        )                    g      ⁡              (        x        )            is a rational function.
Polynomial and rational functions are the only class of mathematical functions that can be evaluated by performing a finite number of arithmetical operations. As a consequence, they are the essential, fundamental and indispensable building blocks of numerical analysis.
As an example, transcendental functions, which include the exponential, logarithmic and trigonometric functions, are typically evaluated inside a computer in terms of polynomial and rational approximations. Such a methodology is the basis for the implementation of transcendental functions in modern microprocessors such as the Intel Pentium and AMD Opteron. The text “Elementary Functions: Algorithms and Implementation, 2nd Edition,” Muller, Jean-Michel, Birkhauser, 2006 describes how to use polynomial and rational approximations to compute transcendental functions in a computer, and it is incorporated herein by reference.
The most efficient method to evaluate a polynomial function is by using Horner's rule, which factors out powers of x, givingf(x)=((anx+an−1)x+ . . . )x+a0.This method minimizes the number of arithmetical operations and results in less numerical instability than a more naïve computational approach.
Although Horner's rule is the most computationally efficient method to evaluate a polynomial function, it has several disadvantages. Namely, the coefficients of the polynomial have little geometric relation to the shape of the curve, and the method is not numerically stable if the coefficients vary greatly in magnitude.
Popular and ubiquitous applications such as desktop publishing, computer graphics, and Computer Aided Design (CAD) put the focus on interactive shape design, that is, the emphasis of the polynomial computations are geometric in nature. This is in contrast to the “algebraic flavor” of Horner's rule and the analytic form of a polynomial as previously presented.
For these reasons, alternative computational methods for polynomials were developed in the 1960's. These innovations were due largely to competition in the automotive industry, occurring over a period of time when the availability of computers and CAD software was replacing traditional paper and pencil design methods.
The breakthrough insight was to use control polygons, a technique that was never used before. The polynomial is defined such that the coefficients are the control points of a control polygon. This innovation greatly facilitates interactive shape design, as changes to the control polygon cause the polynomial curve to follow in a very intuitive way.
Pierre Bezier was the first to publish a mathematical formulation for a polynomial curve which uses the control polygon concept. To this day, such polynomial forms are known simply as “Bezier curves.”
Paul de Casteljau discovered a computational method similar to Horner's rule that evaluates points on a Bezier curve. Known today as the “de Casteljau method,” a point on a Bezier curve is computed by a recursive process of linear interpolation of control points of the control polygon of the Bezier curve.
Last but not least, C. de Boor generalized the de Casteljau method, applying it to the B-spline form of a polynomial and demonstrating that the B-spline is a generalization of the Bezier curve. Known today as the “de Boor method,” a point on a B-spline curve is computed by a recursive process of linear interpolation of control points of the control polygon of the B-spline curve.
As a result, any polynomial can be represented exactly as a Bezier or a B-spline curve. Any rational function can likewise be represented exactly as the ratio of two Bezier or B-spline curves. Formulas to convert the polynomial coefficients to and from Bezier and B-spline form are well known in the art.
Rational functions which are the ratio of two B-spline curves are referred to in the art as NURBS, that is, a Non-Uniform Rational B-Spline. NURBS enjoy “most favored” status in the CAD industry due to their generality and flexibility.
From a computational perspective, the de Casteljau method for evaluating points on a Bezier curve is only slightly more expensive than Horner's rule, but the de Casteljau method is more numerically stable. These qualities, as well as their geometric nature, are the main reason why the Bezier curve and the de Casteljau method are so common and ubiquitous in geometric applications such as desktop publishing, computer graphics and CAD.
The de Boor method for evaluating points on a B-spline curve shares all the positive qualities and benefits of the de Casteljau method, with the additional benefit of increased generality. The de Boor method accounts for the ubiquitous popularity of NURBS in high-end CAD and computer animation applications.
The present invention is specifically concerned with the evaluation of interval polynomials, that is, a polynomial in which the function variable and coefficients are all intervals. More to the point, the interval Bezier and interval B-spline forms of a polynomial are considered.
The common and popular notion of interval arithmetic is based on the fundamental premise that intervals are sets of numbers and that arithmetic operations can be performed on these sets. Such interpretation of interval arithmetic was initially advanced by Ramon Moore in 1957, and has been recently promoted and developed by interval researchers such as Eldon Hansen, William Walster, Guy Steele and Luc Jaulin. This is the so-called “classical” interval arithmetic, and it is purely set-theoretical in nature.
A set-theoretical interval is a compact set of real numbers [a,b] such that a≦b. The classical interval arithmetic operations of addition, subtraction, multiplication and division combine two interval operands to produce an interval result such that every arithmetical combination of numbers belonging to the operands is contained in the interval result. This leads to programming formulas made famous by classical interval analysis, and which are discussed at length in the interval literature.
The application of interval arithmetic to the efficient evaluation of polynomial functions is not straightforward. In fact, it is fraught with many difficult problems and challenges.
Interval dependence is a phenomenon that occurs when an interval variable appears more than once in a mathematical expression. As is well-known by the interval community, interval dependence in a mathematical expression creates a pessimistic result, that is, the result contains excessive interval width. Even worse, pessimism caused by multiple occurrences of an interval variable in an expression is cumulative, that is, pessimism grows as the number of instances of an interval variable in an expression increases.
For an interval polynomial function, that is, a polynomial function where the function variable and coefficients are all intervals, dependence quickly becomes a source of dramatic pessimism. This is due to the number of instances of the function variable, which increase with the degree of the polynomial. The result is an explosive growth of interval dependence and pessimism.
Even the application of Horner's rule, the de Casteljau method, or the de Boor method to an interval polynomial expression does not solve the problem. In all cases, the number of instances of the function variable continues to increase with the degree of the polynomial, and so does the pessimism. As a consequence, it is a widely held belief that interval polynomial functions require expensive “divide and conquer” methods to obtain non-pessimistic results, and a great deal of effort has been dedicated to overcoming pessimism in an interval polynomial function by using such techniques.
The article “Sharp Bounds on Interval Polynomial Roots,” Hansen, E. R. and W. G. Walster, Reliable Computing 8.2, Springer Netherlands, 2002, pp. 115-122 is an example which describes a sophisticated method for computing roots of interval polynomial functions. In the PhD dissertation “Interval Methods for Bounding the Range of Polynomials and Solving Systems of Nonlinear Equations,” Stahl, Volker, Johannes Kepler University, Austria, 1995, the author uses recursive bisection methods in conjunction with a host of ancillary contraction or “tightening” methods to reduce pessimism. Both publications are incorporated herein by reference.
The prior art also includes “pseudo-interval” methods involving polynomial functions. The article “Approximation by Interval Bezier Curves,” Sederberg, T. W. and Farouki, R. T., IEEE Computer Graphics and Applications 12.5, 1992, pp. 87-95 is one such example, and is incorporated herein by reference. A similar example is the paper “Compensated Horner Scheme,” Graillat, S., et. al., Research Report No. RR2005-04, Universite de Perpignan Via Domitia, 2005, which is also incorporated herein by reference.
These so-called “pseudo-interval” methods evaluate an interval result for a polynomial only in the special case of when the function variable is not an interval. In this case, there is less opportunity for dependence to occur, and this makes computing non-pessimistic results quite a bit “easier.” At the same time, because such methods require that the function variable must not be an interval, they are unsuitable for use in true interval analysis problems where the function variable is almost always an interval. Such an example is the interval rendering system and method described in applicant's publication WO 2004/046881 entitled VISIBLE SURFACE DETERMINATION SYSTEM & METHODOLOGY IN COMPUTER GRAPHICS USING INTERVAL ANALYSIS, which is incorporated herein by reference.
In 2001, Miguel Sainz and other members of the SIGLA/X group at the University of Girona, Spain, introduced a new branch of interval mathematics known as “modal intervals.” Unlike the classical view of an interval as a compact set of real numbers, the new modal mathematics considers an interval to be a quantified set of real numbers.
As a practical consequence, a modal interval is comprised of a binary quantifier and a set-theoretical interval. In the modal interval literature, an apostrophe is used to distinguish a set-theoretical interval from a modal interval, so if Q is a quantifier and X′ is a purely set-theoretical interval, then X=(Q, X′) is a modal interval. For this reason, it is easy to see that modal intervals are a true superset of the classical set-theoretical intervals. At the same time, the quantified nature of a modal interval provides an extra dimension of symmetry not present in the classical set-theoretical framework.
This difference allows the modal intervals to solve problems out of the reach of their classical counterparts. Just as the real expression 3+x=0 has no meaning without negative numbers, it can be shown that the interval expression [1,2]+X=[0,0] has no meaning without quantified (i.e., modal) intervals.
The quantified nature of a modal interval comes from predicate logic, and the value of a quantifier may be one of the fundamental constructions ∃ or ∀, that is, “existential” or “universal.” The symbols 3 or V are commonly read or interpreted as “there exists” and “for all,” respectively.
The article “Modal Intervals,” M. Sainz, et. al., Reliable Computing, Vol. 7.2, 2001, pp. 77-111, provides an in-depth introduction to the notion of modal intervals, how they differ from the classical set-theoretical intervals, and upon what mathematical framework they operate; the article is also incorporated herein by reference.
In light of the shortcomings of heretofore known numerical methods, techniques and approaches generally, and the aforementioned inherent challenges with polynomial representations, there remains an unmet need for novel computational systems and methods. More particularly, with the work of Sainz et al. as a backdrop, it remains particularly advantageous to provide a computational system and method for a polynomial where the function variable and coefficients are all modal intervals.